package it.unisa.ingegneria.tdp.esercitazione2;

public class CountingSort {
	//Motodo per l'ordinamento di un vettore di interi con l'algoritmo del Counting Sort
	public static int[] countingSort(int[] source){

		int i=0;
		int dim = getMax(source)  - getMin(source) + 1; //Dimensione del vettore delle occorrenze, in questo modo ottimizziamo la memoria allocata per il vettore
		int[] occurence = new int[dim];
		int[] out = new int[source.length];

		//Calcolo delle occorrenze degli elementi del vettore source, ogni elemento del vettore source viene mappato nella posizione source[i] - getMin(source) del vettore delle occorrenze
		for (i=0; i<source.length; i++)
			occurence[source[i] - getMin(source)]++; 

		//Aggiornamento del vettore delle occorrenze 
		for (i=1; i<dim; i++)
			occurence[i] = occurence[i] + occurence[i-1];		


		for (i = (source.length - 1); i>=0; i--){
			out[occurence[source[i] - getMin(source)]-1] = source[i];
			occurence[source[i]- getMin(source)]--;	

		}

		return out;

	}

	public static int getMax(int[] v) {

		int max = v[0];
		for (int i =1; i<v.length; i++)
			if(v[i] >= max)
				max = v[i];

		return max;
	}

	public static int getMin(int[] v) {

		int min = v[0];
		for (int i =1; i<v.length; i++)
			if(v[i] < min)
				min = v[i];

		return min;
	}

}
